package DemoText;
// 错的
import java.util.Scanner;

/**
 * 最大公约数
 */
public class LuoGuP8792 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = in.nextInt();
        int ret = 0;
        for (int i = 0; i < n - 1; ) {
            if (nums[i] == 1) i++;
            int tmp = Gcd(nums[i], nums[i + 1]);
            nums[i + 1] = nums[i];
            nums[i] = tmp;
            ret++;
        }
        System.out.println(ret);
    }
    public static int Gcd (int x, int y) {
        while (x % y != 0) {
            int tmp = x % y;
            x = y;
            y = tmp;
        }
        return y;
    }
}
